﻿//【进阶】37.位图和布隆过滤器
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"HashTable.h"
#include"BloomFilter.h"

//【命名空间】

//【类声明】

//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	cout << "****主函数开始****" << endl;
	Test1();
	Test2();
	Test3();
	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】

/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	CLOSE_HASH::TestHashTable_Closed();
	OPEN_HASH::TestHashTable_Open1();
	OPEN_HASH::TestHashTable_Open2();
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	//思考1：40亿个不重复无符号整数没排序，给一个无符号整数作为目标，如何快速判断是否在这40亿中
	//40亿整数 1个整数4个字节=160亿字节 10亿字节是1G,总计需要16G空间
	//答：1.拆分40亿分为400份每份1000万或更细分，依次遍历每组
	// 2.拆分为多组进行排序，每组有一个区间，筛选出符合区间的组二分查找
	// 3.set/unordered_set(红黑树、哈希表)存起来查找
	//以上方法都有问题就是海量数据处理，内存不够 
	// 更高效的办法是采用
	// 假设空间足够，则采用直接定值法查找，需要开约42亿个空间直接存储每个值
	// 但是上面提出空间是主要问题，所以可以将一个数的存在与否定义为0或1，
	// 这样可以以一个比特位的状态，大约需要16/4/8大约需要500多MB空间
	// 这种方法叫做位图，即节省了空间，效率也非常高
	myspace::Testbitset();
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	myspace::TestBloomFilter();

	//思考2：100亿个整数设计算法找出只出现一次的树
	//创建一个包含所有整数的位图
	// 增加一个判断标记判断条件：如果一个数存在了1次会被标记为0、如果存在超1次会被标记为1
	// 一个数占2个位三种状态//00不存在 01出现一次 11出现2次以上
		
	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//哈希表空间大小的问题
	// 在测试后技术人员发现如果把哈希表的空间大小设置为素数时，出现哈希冲突的概率会显著降低
	// 所以插入是空间调整可以不使用原式： size_t newindex = HashFunc(koft(cur->_data)) % newtables.size();
	// 结合素数表调整空间容量
//【进阶】37.位图和布隆过滤器
	//位图的优点，节省空间、效率高，缺点是只能处理整形
	// 对于位图的缺点，可以将位图和哈希表结合，即布隆过滤器
	// 布隆过滤器
		//表示一个内容是否存在可以用1个位来标记，但是不同字符串可能会映射到相同位置，出现误判
		// 而布隆过滤器是采用【一个值映射多个位置】来降低误判概率
		// 布隆过滤器大部分的场景都是字符串类型的值
		// 一般布隆过滤器不支持删除或reset
		//优点：节省空间、高效
		//缺点：存在误判，不支持删除 

		









